package leetcode_301_400;

public class LeeCode_306 {
    public static void main(String[] args) {
//        System.out.println(isAdditiveNumber("112358"));
//        System.out.println(isAdditiveNumber("1991020199"));
//        System.out.println(isAdditiveNumber("1023"));
//        System.out.println(isAdditiveNumber("101"));
//        System.out.println(isAdditiveNumber("1203"));
        System.out.println(isAdditiveNumber("1999999999999999910000000000000000"));
        System.out.println("10000000000000000".length());
        System.out.println(Long.MAX_VALUE);
    }
    private static boolean isAdditiveNumber(String num) {
        int n = num.length();
        for (int i = 1; i < 15; i++) {
            if (i >= n)
                break;
            for (int j = i + 1; j < i + 15; j++) {
                if (j >= n)
                    break;
                Long pre = Long.parseLong(num.substring(0, i));
                Long last = Long.parseLong(num.substring(i, j));
                if (num.charAt(i) == '0'){
                    if (dfs(pre, last, num.substring(j))){
                        return true;
                    }
                    break;
                }
                if (dfs(pre, last, num.substring(j))){
                    return true;
                }
            }
            if (num.charAt(0) == '0'){
                break;
            }
        }
        return false;
    }
    private static boolean dfs(Long pre, Long last, String next){
        if (next.length() == 0)
            return true;
        for (int i = 1; i < 15; i++) {
            if (i > next.length()) {
                break;
            }
            long goal = pre + last;
            long maybe = Long.parseLong(next.substring(0, i));
            if (next.charAt(0) == '0'){
                if (maybe == goal && dfs(last, maybe, next.substring(i))){
                    return true;
                }else {
                    break;
                }
            }
            if (maybe == goal){
                if (dfs(last, maybe, next.substring(i))) {
                    return true;
                }
            }
        }
        return false;
    }
}
